


// 二叉树的层平均值
class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);
        vector<double> ret;
        while(q.size())
        {
            int k = q.size(), n = k;
            double sum = 0;
            while(k--)
            {
                TreeNode* front = q.front();
                q.pop();
                sum += front->val;
                if(front->left)
                    q.push(front->left);
                if(front->right)
                    q.push(front->right);
            }
            sum = sum * 1.0 / n;
            ret.push_back(sum);
        }
        return ret;
    }
};




// 二叉树的最小深度
class Solution {
public:
    int minDepth(TreeNode* root) {
        if(!root) return 0;
        int left = minDepth(root->left);
        int right = minDepth(root->right);
        if(left == 0 || right == 0) return max(left, right) + 1;
        return min(left, right) + 1;
    }
};
